m
A CLASS OP PINITE COMPUTATION STRUCTURE!
SUPPORTING THir PAST POURIER TRANSFORM
Richard J. Bonneau
MAC Technical Memorandum 31
March 1 973
Work reported here is supported in part by the Raytheon Advanced
Decree 'Program, and by Project MAC, an. M.I.T. research program
sponsored bv the Advanced Research Projects Agency, Department of
Defense, under ARPA Order No. 2095 and under Office of Naval
Research Contract Number N00014-70- A-0362-0006 and the National
Science Foundation under contract number GJCO-43'27.
Massachusetts Institute of Technology
PROJECT MAC
Cambridge Massachusetts 02139
rr-y'i-
SHflUTOUflTB. HOITA'IU'IMOO 3TIHn 10 2$AJD A
oM .1. fnaifolft
;ipfe
rj ajjbnjrtomsM Isoiarfos? 0AM
£V°r &rm
»T*X*M 'iH'^aNyt . #»jfcflrt<I . t^ bos i<ist3©*5 9€»i^an
■tim m t tfl beoaavbk sett ^ef Jtoroaabqa
3& «£$ EO A1HA os&fw « satiated
tf! TadmM *mtSsK& rtoommsi
ill • te&Mtim *Wbm mk3aixw<fiL aonaioP,
8^rS0 aJJsauriasaasM
DAH taSiQSt:
s^JticrssO
PACE 2
Section I,- Introduction
The Fast Fourier Transform (FFT) and modular arithmetic are
two distinct techniques which recently have been employed to
increase the efficiency of numerous algorithms in the area of
symbolic and algebraic manipulation. Motivated by work done on
fast large integer multiplication by Schonhage and Strassen [11]
and by Knuth [7], this paper analyzes the question of when these
two techniques can be utilized concurrently. The desirability of
the convolution property of the EFT suggests a practical
definition for the support of an FFT, while a generalization of
the modular rings of integers motivates a reasonable definition
of a finite computation structure. A Finite Computation
Structure is defined to be a commutative ring with unity, and of
finite, — non-zero characteristic. This report first completely
characterizes the modular rings of integers which support the FFT
by considering the prime factorization of the modulus. This
characterization is then extended to provide the following
result: Theorem ; Let R be a finite computation structure of
characteristic in. Then R will support a K-point ITT if K divides
p-1 for each prime p dividing m. The paper then concludes with
examples of the application of this result to the problems of
computing products and powers of symbolic multivariate
polynomials.
Section 2. The Discrete Fourier Transform
Def inition ; Let R be a commutative ring with unity, written as
T: — K an integer > 1, and WK an element of R of order K; i.e., a
primitive K-th root of unity. Then the DISCRETE FOURIER
TRANSFORM (DFT) of the K-sequence (a0,a1,.. .,a(K-i;j is the K-
sequence
(ao,ai,...,a(K-i))
given by the following equations:
a = } a V/ 1 2 0<j<K-1 (1)
/ . i K
2
PAGE 3
Definition ; Assuming the same conditions as above, and also,
that K possesses a multiplicative inverse in R (i.e. 1/K), then
the INVERSE DISCRETE FOURIER TRANSFORM (IDFT) of the K-sequence
(a0,a1,... ,a(K-ljJ is the K-sequence
(ao,ai,...,a(K-i))
given by the following equations:
a = (1/K)
/ a W
/ - - \ • i K
»i = Q
0<i<K-1 (2)
If we consider the term ai*WK**(-i*j) to be rewritten as the
equivalenit term
v i ai*WK**((K-i)*j)
:/
then we can rewrite the above equation as
K ■- 1.
a = (1/K)
} a W
/ K-i K
i =
r
(la)
If we now define a(K) = a(0), then the inverse DFT can be
computed from the DIT by merely "flipping" the input sequence.
Here, flipping consists in replacing the i-th term by the (K-i)-
th term. Thus the same computational algorithm (for the DFT) can
be used to compute both the DFT and the IDFT. As might be
expected from the terminology, under the right conditions, the
two transforms are inverses of each other, and thus provide
different representations of K-sequences. The remainder of this
paper will be concerned with determining some of the "right"
conditions under which the DFT can be inverted. Note, also, that
the DFT (and the IDFT) are linear transformations from R**K to
R**K, (where R**K is the ring of K- tuples of elements of R with
component addition and multiplication) since the quantities
WK**(i*j) are all "constants" for each application of the DFT.
For more information on this approach to the phenomenon of the
DFT, see Nicholson [10].
The computation of the DFT by classical techniques usually
involved 0(K**2) operations, as the computation of each
PAGE 4
transformed element took K multiplications followed by K-1
additions. However, Cooley and Tukey [5] demonstrated a
computation scheme by which the DIT of a K-sequence could be
computed in only 0(K log K) operations* This method has become
known as the fast Fourier Transform (EFT). The key concept in
the reduction of the computation time involves the fectofization
of K. In other words, for K highly composite, the DFl|c«m be
computed by forming sub-sequences of the original sequence,
performing a DFT of fewer elements on them, then assembling the
resulting sequences* The goal here is not to develop the theory
surrounding the FFT (see Cooley-Tukey [5]) but rather to instill
some feeling for the immense efficiency of this algorithm and
thus to motivate the desire to find as many ways as possible in
which it can be i nvoked* During the remainder of this paper, the
terms DPT and FFT will he used interchangeably, as they refer to
a computation function and a computation algorithm which
correspond to each other.
The particular virtue of the DFT in many applications results
from the following:
Definition ; Let A = (a0,a1,.. *,a(K-1)) and B = (b0,b1,.. .,t(K-
1)) be two K-sequences in R. Then the CONVOLUTION OF A AND B,
written A*B, is the K-sequence C = (cO,d,.* . ,c(K-l )T~where tHe
cj are defined as follows:
K - 1,
c = \ a b 0<|cK-1 (3)
2 * > i j-i T
i =
where bn for n < is defined as b(n+K).
Convolution Property of the DFT :
Let A and B be as in the preceding definition. Let A* and B* be
the DFT's of A and B respectively. Then the following equation
is true:
(A*B)' = A* x B* (4)
where $, x" means component-wise multiplication of K-sequences* In
other words, the DFT transforms the convolution operation in R**K
into the component-multiplication in R**K, according to the
following commutative diagram:
DFT x DFT
R**K x R**K > R**K x R**K
i
i
EFT J
R**K > F**K
A A
Jt
QED.
PAGE 5
1,
As a result of (4), the convolution of two K-sequences can be
computed in the following way:
1)compute the transforms A" and B* of A and B
respectively.
2) perform componentwise multiplication on A** and B*
to obtain a K-sequence C".
3) perform the inverse DFT on C to obtain the
convolution sequence C.
Thus, the DPT provides a method (though not an intuitive one) for
computing the convolution of sequences, assuming that the inversr
DFT of step 3 is possible; i.e., if we can turn the bottom arrow
around in the above figure* What this requirement amounts to is
that we must able to compute a *true n inverse DFT.
Let us now look into the requirements for the invert ibility of
the DFT. If we apply the inverse DFT of equation 2 to the
sequence of elements computed via the DFT of equation 1 f the
PAGE 6
Inasmuch as the following quantity appears quite frequently in
- " lie ■
IX
following equations ..will hold:
As a result, the IDFT, as defined originally, will be a true
inverse <«=> a"hat-hat sub 1" = a«sub 1" for all 1 < K-+1 <==>
(Recall that delta(i,j) = 1 if i=j and 0. otherwise.) Notation:
Inasmuch as the following quantity appears quite fr«
the rest of this paper, we use the following notation:
S. * * u
Using this notation, wwe obtain the requirement: The IDFT is an
inverse <=> S"sub 1" = K delta(0,l ). Thus, a reasonable basis
upon which to build a useful DFT (i.e., one able to produce the
convolution) is to define:
Definition : Let K be > 1 . The Support , of a K-point DFT is a
commutative ring R with identity such tnat
:S1) There exists ,1/K in R.
S?) There exists wK in R whose order = K.
[S3) S"sub 1" s K delta(0,l) for all 1 < K-1.
Note that the support of an ITT is an "essential" property of a
ring ; i.e., if a ring R supports a K-point FFI and R is
contained in a larger ring R', then R' also supports K-point
EFT's.
Two examples of support of a K-point EFT are thecomplex numbers
with wK being the complex number cos(2T^K)+f-i sm(2^K), and
also the algebraic number field Q[t1, where * is a formal
solution to the equation x**K = 1, and'Q is the field of rational
numbers.
Section 3. Finite Computation Structures
This section deals with the problem of developing a sufficiently
rich generalization of the structure of modular rings of
PAGE 7
integers* The motivation for this generalization derives from
the desire to develop data structures whose underlying arithmetic
is precisely modular arithmetic* This will enable the modelling
of a data structure within a computer. As a result of this
thinking, we propose the following:
Definition : A finite Computation Structure is a commutative ring
with unity, having finite, non-zero characteristic • (Recall that
the characteristic of a ring is the smallest integer m such that
ma = for all a in the ring. See Lang [8] and Albert [1].)
If the above definition holds, we say that R is a finite
computation structure (fcs) of characteristic m. It can easily be
shown that if R is an fcs of characteristic m, then there exists
a subring S in R which is isomorphic to the integers modulo m
(Z/mZ). Thus the finite computation structure concept
encompasses the class of all modular rings of integers.
Examples :
Z/mZ for all integers m.
(Z/mZ)[x1,x2,...,xn] for all m and all n.
(Z/mZ)**n for all m and all n, where multiplication is
component multiplication.
4) (Z/mZ)**n for all m and all n, where multiplication is
convolution of n- tuples.
5) GE(p**n) (field of p**n elements) for all primes
p and all integers n > 0.
Section 4* Characterization of Modular Rings of Integers
In order to characterize the class of finite computation
structures vis-ar-vis the PFT, it is first necessary to consider
the case of modular rings of integers inasmuch as one of these
rings is embedded in every fcs. The goal of this section is to
characterize those modular rings of integers which support a K-
point EFT. In order to do this, we will draw upon work down by
Pollard [11 ]• In his work, Pollard puts forth necessary
conditions for the support of FFT's in modular rings of integers
(Theorem A). The method of this section is to prove the converse
of Pollard's result (Theorem B), eliminate a case untouched by
Pollard (Theorem C), and finally, remove unneeded hypotheses from
the resulting equivalence (Theorem D). For the proofs given in
this section, the author assumes the reader to have basic
understanding of elementary number theory (as in Grosswald [6])
and elementary group theory (as in Birkhoff and Mac-Lane [2]).
Note: In the remainder of the paper we will use the following
notational conveniences:
PAGE 8
Printed
Pi
ei
pi**ei
Zm
Zpi**ei
Z(m)
Z(pi**ei)
wK
Theorem A:
Written
cPC-mj
Pollard's theorem.
Meaning
p sub i, a prime number
e sub i, a positive integer
p sub i to the e sub i power
The ring of integers irodulo m
The ring of integers modulo
the ei-th power of the prime pi
The multiplicative group of Zm
The multiplicative group cf Zpi**ei
phi of m, the Euler phi-function
K-th root of unity
Let m be odd and
If K divides pi-1 for every prime pi dividing m, and if there
exists an element wK in Z(m) such that the order of wK in
Z(pi**ei) is precisely K for all i, then the modular ring Zm will
support a K-point EFT.
Proof : In order to prove this result, we go back to the
requirements for K-point FIT support*
(SI ) Since K divides each pi-1 for all i, then K and pi are
relatively prime for all i. This implies that K is
relatively prime to the powers of the pi's and also to
the product of the powers of the pi's. Hence, K is
relatively prime to m. This implies that K possesses an
inverse in Zm.
(S?) Ey hypothesis, there is an element wK of order K for each
Zpi**ei. Then, this element also has order K within Zm.
(S3) The case for 1=0 is trivial. The proof for 1^0 depends
heavily on:
Lemma A: Assume the above hypothesis with
assumption that m=p**e for some prime p. Then
point ITT.
the additional
Zm supports a K-
Proof of Lemma ;
(51) K divides p-1 and thus, K and p are relatively prime.
result, K has an inverse in Zp**e.
(52) By hypothesis, there exists an element wK of order
Zp**e.
(53) Again, the case 1 = is trivial, so we assume 1 is
zero. Consider nov; the expressions for S"sub 1".
know that wK**Kl=£ M sub 1" (wK-1). Clearly, the left hand
side of the above equation is zero as wK is a K-th root
of unity. We need only show that S M sub 1" = (modulo
p**e). We can do this by showing that wK-1/0 (module p)
for then p**e would divide S"sub 1". Now, if wK = 1
As a
K in
non-
We
PAGi: 9
f.
(modulo p) then (wK,p)=1 and hence wK would be an eleirent
of the subgroup {w in Zp**e such that (w,p)=1} of
Z(p**e). This subgroup has order p**(e-1) and Z(p**e)
has order (p-1 )p**(e-1 )• But wK is also an eleirent of
the cyclic subgroup of Z(p**e) of order K consisting of
all the powers of wK. Hence, wK is a common element of
two subgroups of Z(p**e) having relatively prime orders,
hence the identity. Thus, wK = 1 (modulo p**e) .
Contradiction. Thus, wK ^ 1 (modulo p) and S^sut 1" =
(modulo p**e).
QED for Lemma.
To continue with the proof of the Theorem, we now let m =
prod(pi**ei,i,1,r) where the pi are distinct primes. By lemma A,
we know that Zpi**ei will support K-point EFT's for each i. In
particular, S M sub 1" = (mod pi**ei) for each i. By using the
Chinese Remainder Algorithm (see Lipson [9] for an excellent
discussion of the various Chinese Remainder Algorithms) on the
relatively prime moduli pi**ei, we know that S°sub 1" - (modulo
prod(pi**ei,i,1 ,r) ) ; i.e. , (modulo m) . Thus the three
conditions are satisfied and Zm supports K-point JTT's.
QED.
The next Theorem presents the converse to Theorem A and as such
characterizes completely the odd numbers which can support K-
point EFT's .
Theorem B: If Zm supports K-point EFT's and m =
prod(pi**ei,i,1,r), m odd, then K divides pi-1 for all i and
there exists an element wK in Zm such that wK is of order K in
Z P i**ei for all i.
Proof : Since Zm supports K-point FFI's, then by S1, K has an
inverse in Zm and hence K and m are relatively prime. It follows
that K and pi are relatively prime for each i. Thus, K does not
divide pi for all i. Next we can show that the map
p :Zm >TTZpi**ei
given by <Ax) = (x mod p1**e1,x mod p2**e2,.. .,x mod pr**er)) is
a ring isomorphism and thus induces a group isomorphism between
Z(m) and TT z (pi** ei )- first note that the order of Z(*) is
«$c^ = <$<.Tj;-f\ e ') * -jr sup;") s£h f .-■vp^"'
whereas the order of Z(pi**ei) is given fcy
£tf; ") - c^.-i^i
PAGL 10
We know that if wK has order K in Z(m), then K must divide the
order of Z(m). Since K does not divide any pi, then K divides
the product prod(pi-1,i*1,r). However, we now show that K
divides each factor pi-1. By the 3rd requirement for K-pcint FFT
support (S3) 5 we are guaranteed that S M sub 1" = (modulo m =
pi**ei), for all 1 < K-1 and not zero. Since the pi**ei are all
relatively prime, "Dien S"sub l a = (modulo pi**ei) for all i.
Now consider the order of wK in Z(pi**ei), say K1. Clearly, K1
divides K. If K1 does not equal K then S"sub K1 M = 1+wK**K1+
wK**2K1+...=1 +1+1... =K (modulo pi**ei), since the order cf wK is
K1 . But K and pi**ei are relatively prime for all pi and hence K
^ (modulo pi**ei). We are then left with the conclusion that
if K1 ? K, then S M sub K1" ^ (mod pi**ei), which is a
contradiction. Thus, wK has order K in each Z(pi**ei). Thus, K
divides the order of the group, i.e., (pi-1)pi**(ei-l). Since K
and pi are relatively prime, then K divides pi-1 for every i.
QED.
Having finished categorizing completely the case of odd moduli,
we consider now the possiblity of even moduli supporting K-pcint
FFT's. This possibility is discarded by the following theorem.
Theorem C ; No even modulus can support an EFT.
Proof : We assume here that K is non-trivial; i.e., K > 1. In
order to support a K-point FFT with a modulus m which is even, we
must have that K possesses an inverse in Zm. This condition is
equivalent to saying that K and m must be relatively prime and
hence that K must be odd. If there exists an element wK in Zm of
order K, where we now write m = prod(pi**ei,i,1,r) with p1=2,
then by means of the isomorphism described in Theorem B, the
order of wK in Z(2** e 1) must divide K. However, since the order
of Z(2**e1) is 2**(e1-1), the order of wK in Z(2**e1) can only be
even or«1. It can not oe even as it must divide K. Thus we are
left with the fact that the order of wK in Z(2**e1) must be 1;
i.e., wK = 1 (modulo 2**e1). In order to complete our proof we
look at the possible cases for m:
Case 1 : m= 2**e1 .
In this case, wK has order 1 in Zm = Z2**ei and hence
cannot have order K.
Case 2: m = ml * 2**e1 where ml is odd.
If we now invoke condition S3 for FFT support, then S f, sub
1" must = (modulo ml * 2**e1). Since ml and 2**e1 are
relatively prime, this implies that S*sub 1 M = (modulo
2**e1) for all 1 < K. If we now look at S f, sub 1 w however,
we find that S"sub 1" = 1 + wK + wK**2 + ... =1+1+1
+ .. .. (modulo 2**e1) (since wk =i1 (modulo 2**e1)) = K
(modulo 2**e1), which is not equal to 0, as K is odd.
PAGE 11
Thus, S w sub i1 M is not zero and we have a contradiction.
Since both cases yield a contradiction, we have the result that
even moduli cannot support FFT's.
QED.
The last theorem in this section combines all the results of this
section and provides for the complete characterization of modular
rings of integers which support the ITT.
Theorem D: Zm supports K-point FFT's if and only if K divides
pi-1 for every prime pi dividing m.
Proof * Using theorems A,B and C, we see that we need only prove
the following assertion in order to obtain the above result:
If K divides pi-1 for all primes pi dividing m, then there exists
an element wK in Zm of order K in each Z(pi**ei) (and hence in
Zm).
The argument proceeds as follows:
1. Every Z(pi**ei) possess primitive roots^of unity;
i.e., elements ri of order the same as Z(pi**e
which is (pi-1)pi**(ei-1). (See Grosswald [6]
2. The element wi defined by
has order K in Z(pi**ei) since K divides pi-1
and order(ri**n) = order (ri)/gcd(n, order (ri)) = K,
where
-C*£-)r. e <-'
3. The element wK which is the unique solution (modulo m)
to the following family of congruences:
wK =.wi (modulo pi**ei) i =1,...,r
is an element of order K in Z(pi**e}) for all i
and thus of order K in Zm.
Thus we see that if the hypothesis holds, we can always find an
element of the desired order. As a result, the hypothesis of
existence of K-th roots of unity in the equivalence implied by
Thorems A, B and C is redundant.
A final remark concerns the removal of the hypothesis for odd
primes from Theorems A and B. Inasmuch as K must divide pi-1 for
each i and that K is not 1, ther the statement that the pi must
PAGE 12
be odd is redundant. With the two removals of restrictions as
described above, the equivalence of Theorems A, B and C result in
exactly the statement of Theorem D.
QED.
Summary ; Utilizing the various theorems presented in this
section, we have provided a complete characterization of modular
rings of integers supporting the last Fourier Transforms.
Examples :
TZ z3~"can support only 2-point FFT's (with wK = -1).
2. Similarly, Z3**e can only support 2-point FFT's for all e.
3. 8-point FFT's can be performed in Zm for any m
of the form prod((8ci+1)**ei,i,1,r) for arbitrary
r and ci, where 8ci + 1 is prime.
e.g., 1 7**e , 33**e ' , 1 7**e * 33**e ' .
Section ]?: Extension to Finite Computation Structures
As we have seen in section 4, only certain modular rings will
support K-point FFT's. We now extend this result to include some
of the finite computation structures.
Theorem ; If R is a finite computation structure of
characteristic m, then R supports a K-point FIT if K divides p-1
for every prime p dividing m.
Proof ; Let K divide p-1 for all primes p dividing m. Then by
Theorem D we know that Z/mZ supports a K-point FFT. As a result,
the requirements S1, S2 and S3 of section 2 hold in Z/mZ. Since
R is an fcs of characteristic m, then there exists a subring S of
R isomorphic to Z/mZ. Because all of the requirements for
support of an FFT involve only ring operations, then any
isomorphic copy of Z/mZ will satisfy the support requirements.
Thus S supports K-point FFT's. However, the definition of
support is essential and thus R also supports K-point FFT's.
QED.
Note; If S";Z/mZ > R is the isomorphism onto a subring of R,
then 0"(wK) is a K-th root of unity in R. Thus, knowledge of
modular K-th roots of unity will be sufficient to compute FFT's
in R.
PAGE 13
Section 6: Applications
The results presented have been applied to the problems of
computing products and powers of symbolic multivariate
polynomials over the integers (see [3] and [4]). The following
brief example examines the application of the IFI in a finite
computation structure to the computation of products of
polynomials.
Let f and g be univariate polynomials over some coefficient ring
R, with the degree of f = m and the degree .of g = n. We csn thus
write:
f t*> = Q + °S* +" Q 4 * l + ' ' ' t 0^ %**
The product polynomial h(x) = f (x)*g(x) can then be written as
h C*N t Co ««- c,* + Ct-v* + • • • + ^H,♦K^ ,, ' +,,
where the coefficients ,ci are computed by
If we set K = m+n+1 and form 2 K-sequences
A - H , *,, • ••, <U, ©, ■ ••, O)
then the K-sequence C given by
£ =. Ct , C,, • •• , C^, 4>1 ^
is precisely the convolution of A and B, as defined in Section 2.
As a result of this observation, if the coefficient ring R
supports K-point FFT's, the the product polynomial, h(x) can be
computed using FFT's as follows:
1) form the 2 K-sequences A and B
2 j Apply a K-point FFT to each sequence, yielding A and B
3) Multiply A and B component- wise, yielding int.
4; Apply the inverse K-point FFT to obtain C, which is
the sequence of coefficients of the product
polynomial h.
In particular, if the coefficient ring is the integer, we cannot
perform ITT's as there are no roots of unity other than 1 and -1.
However, if the largest coefficient (in absolute value) in A, B
or C is bounded by M, then we can embed f(x) and g(x) in the
polynomial ring Zm[x], where m > 2M and Zm supports K-point
PAGE 14
f!FT*s„ Then, the application of the 4 steps mentioned abcve will
compute the product
However, since the maximum coefficient is less than m/2, then
h(x) = f(x)g(x) and we are finished*
Similarly, if the coefficient ring R = Z[y] (i.e*: f and g are
bivariate polynomials in x and y over the integers), we can embed
f and g in Zm[x,y] where m is sufficiently large and Zr[y]
supports K-point FFT s* Again, application of the 4 steps given
above will yield a polynomial
but since m is chosen appi^opriatdly, h(x,y) actually equals
f(x,y)g(x,y).
The computation of powers of polynomials proceeds in an analogous
manner* Studies performed on these two computation©!- problems
have indicated that the FIT methods provide significant
improvement in the efficiency of these algorithms for a large
class of polynomials* (See Bonneau [3] [4]).
Section 7: Summary _
This paper has presented several results relating modular
arithmetic schemes and the Fast Fourier Transform* In
particular, the classes of modular rings of integers in which the
FFE may he computed is completely characterized by the prime
decomposition of the modulus* Also, an extension of this result
for computation structures similar to modular rings of integers
yields a sufficiency hypothesis for the computation of FFT*
Further research in this area might be motivated by the desire to
find necessary and sufficient conditions for FIT support in
finite computation structures or in general rings* As an
example, Nicholson [10], using the definition of FFT to be a
transformation which takes "convolution-product" rings into
"component-product" rings, provides the result that FFT's are
supported in division rings (i*e*, rings with no zero divisors)
iff the ring contains a particular primitive root of unity* It
would be most desirable to extend this type of result to a larger
class of rings*
PAGE 1
References
[I] Albert* Fundamental Concepts of Higher Algebra * University
of Chicago Press* 1956* r
[2] Birkhoff & Mac Lane. A Survey of Modern Algebra * Third
edition. MacMillan Co* 1 9bt> .
[3] Bonneau. "Polynomial Multiplication and The Past Pourier
Transform* M Department of Mathematics, Mass. Institute of
Technology , Cambridge, Mass. 1973. (In preparation)
[4] ^ "Polynomial Exponentiation: The Past Pourier
Transform Revisited", Department of Mathematics, Mass.
Institute of Technology, Cambridge, Mass* 1973* (In
preparation)
[5] Cooley & Tukey. "An Algorithm for the Machine Calculation of
Complex Pourier Series." Mathematics of Computation, vol.
19, April 1965. pp. 297-WI
[6] Grosswald. Topics from the Theory of Numbers . Macmillan
Company, New xork* 196b. Chapter TT
[7] Knuth* The Art of Computer Programming — Errata et Addenda *
Computer Science Department, Stanford University . Jan.,
1971- pp. 21-26.
[8] Lang* Algebra * Addison-Wesley Co., Reading, Mass. 1965.
[9] Lipson. "Chinese Remainder and Interpolation Algorithms,"
Proc . of Secon d Symposium on Symbolic Algebraic
Manipulation , March 19717^
[10] Mcholson. ^Algebraic Theory of Finite Pourier Transforms* 11
Journal of Computer and System Sciences , vol. 5» 1971.
pp— 52 4 ~ 53F7T
[II] Pollard. "The Past Pourier Transform in a Pinite Field."
Mathematics of Computation , vol* 25 » number 114, April,
>WHZ pp7 "36b - 374.
[12] Schonhage & Strassen* "Fast Multiplication of Large
Numbers," to appear in Computing *
UNCLASSIFIED
Security Classification
DOCUMENT CONTROL DATA -R&D
(Security classification of title, body of abstract and indexing annotation must be entered when the overall report is classified)
1 . ORIGINATING ACTIVITY (Corporate author)
MASSACHUSETTS INSTITUTE OF TECHNOLOGY
PROJECT MAC
2fl. REPORT SECURITY CLASSIFICATION
UNCLASSIFIED
2b. GROUP
NONE
3. REPORT TITLE
A CLASS OF FINITE COMPUTATION STRUCTURES SUPPORTING THE FAST FOURIER TRANSFORM
4. DESCRIPTIVE NOTES (Type of report and inclusive dates)
INTERIM SCIENTIFIC REPORT
5- AU THOR(S) (First name, middle initial, last name)
RICHARD J. BONNE AU
6- REPORT DATE
MARCH, 1973
8a. CONTRACT OR GRANT NO.
N00014-70-A-0362-0006
b. PROJEC T NO.
la. TOTAL NO. OF PAGES
15
7b, NO. OF REFS
12
9a. ORIGINATOR'S REPORT NUMBER(S)
9b. OTHER REPORT NO(S| (Any other numbers that may be assigned
this report)
NONE
10. DISTRIBUTION STATEMENT
DISTRIBUTION OF THIS DOCUMENT IS UNLIMITED
11. SUPPLEMENTARY NOTES
12. SPONSORING MILITARY ACTIVITY
OFFICE OF NAVAL RESEARCH
13. ABSTRACT
The Fast Fourier Transform (FFT) and modular arithmetic are two distinct
techniques which recently have been employed to increase the efficiency of
numerous algorithm in the area of symbolic and algebraic manipulation.
Motivated by work done on fast large integer multiplication by Schonhage and
Strassen [11] and by Knuth [7], this paper analyzes the question of when these
two techniques can be utilized concurrently. The desirability of the convolution
property of the FFT suggests a practical definition for the support of an FFT,
while a generalization of the modular rings of integers motivates a resonable
definition of a finite computation structure. A Finite Computation Structure
is defined to be a commutative ring with unity, and of finite, non-zero charater-
istic. This report first completely characterizes the modular rings of integers
which support the FFT by considering the prime factorization of the modulus.
This result: Theorem : Let R be a finite computation structure of characterizatioi
m. Then R will support a K-point FFT if K divides p-1 for each prime p
dividing m. The paper then concludes with examples of the application of this
result to the problems of computing products and powers of symbolic multivariate
polynomials.
L
DD F N°o R v M e 5 1473
S/N 0102- 01 4- 6600
(PAGE 1 )
UNCLASSIFIED
Security Classification
UNCLASSIFIED
Security Classification
K EY WORDS
Fast Fourier Transform
Finite Computation Structures
Modular arithmentic
Symbolic polynomial manipulation
DD, F ,r..1473 back)
'PAGE 2)
UNCLASSIFIED
Security Classification
,*;W:
MIT/LCS/TM-31
A CLASS OF FINITE COMPUTATION
STRUCTURES SUPPORTING THE
FAST FOURIER TRANSFORM
Richard J. Bonneau
March 1973
PUBLICATIONS DISTRIBUTION
PROJECT MAC, ROOM 417-A
MASSACHUSETTS INSTITUTE OF TECHNOLOGY
545 TECHNOLOGY SQUARE
CAMBRIDGE, MASS. 02139
March 1973
We have recently issued Project MAC Technical Memorandum TM-31:
A Class of Finite Computation Structures
Supporting the Fast Fourier Transform
Richard J. Bonneau
AD 757-787
ABSTRACT
The Fast Fourier Transform (FFT) and modular arithmetic are two
distinct techniques which recently have been employed to increase the
efficiency of numerous algorithms in the area of symbolic and algebraic
manipulation. Motivated by work done on fast large integer multiplication
by Schonhage and Strassen [11] and by Knuth [7], this paper analyzes the
question of when these two techniques can be utilized concurrently. The
desirability of the convolution property of the FFT suggests a practical
definition for the support of an FFT, while a generalization of the
modular rings of integers motivates a reasonable definition of a finite
computation structure* A Finite Computation Structure is defined to be a
commutative ring with unity, and of finite, non-zero characteristic.
This iceport first completely characterizes the modular rings of integers
which support the FFT by considering the prime factorization of the
modulus. This result: Theorem : Let R be a finite computation structure
of characterization nu Then R will support a K-point FFT if K divides
p-1 for each prime p dividing m. The paper then concludes with examples
of the application of this result to the problems of computing products
and powers of symbolic multivariate polynomials.